↓Skip to main content

Modular Arithmetic

·3 mins
Mathematics
A modulo 12 clock
Table of Contents

What is Modular Arithmetic? #

Modular arithmetic is a special type of arithmetic where numbers wrap around after a fixed value. For example, in a clock with 12 hours, numbers like 12, 24, 36, etc., are all equivalent to 0 modulo 12. We say that 24 is congruent to 0 modulo 12, meaning that 24 leaves a remainder of 0 when divided by 12. Mathematically, we write this as \( 24 \equiv 0 \pmod{12} \).

Generally, we say that an integer \( a \) is congruent to another integer \( b \) modulo \( m \) if \( a - b \) is a multiple of \( m \), and we write \( a \equiv b \pmod m \). We compute the remainder using the modulo operator: \(a \bmod m = r \).

In other words, if the remainder of \( a \) divided by \( m \) is the same as the remainder of \( b \) divided by \( m \) (\(a \bmod m = b \bmod m \)), then \( a \) is equivalent (or congruent) to \( b \).

For example:

  • \(2 \bmod{12} = 2 \)
  • \(14 \bmod{12} = 2 \)
  • \(26 \bmod{12} = 2 \)

Therefore 2, 14, and 26 are all equivalent to each other modulo 12. They occupy the same position in the cyclic structure of remainders modulo 12, see the clock image above. This cyclic structure is the reason why sometimes modular arithmetic is called “clock arithmetic”.

Key Properties #

  1. \( (a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m \)
  2. \( (a - b) \bmod m = (a \bmod m - b \bmod m) \bmod m \)
  3. \( (a \cdot b) \bmod m = (a \bmod m \cdot b \bmod m) \bmod m \)
  4. If \(a \equiv b \pmod m \) and \(c \equiv d \pmod m \) then \(a + c \equiv b + d \pmod m \)
  5. If \(a \equiv b \pmod m \) and \(c \equiv d \pmod m \) then \(a \cdot c \equiv b \cdot d \pmod m \)
  6. An integer \(a\) has an additive inverse modulo \(m\) denoted \( -a \pmod m \) such that \( a + (-a) \equiv 0 \pmod m \).
    Then \( -a \equiv m - (a \bmod m) \pmod m \).
    This holds because \(a + (m - a) = m \equiv 0 \pmod m \).

Can \(a \bmod m = m \)? #

No. By definition, \(a \bmod m = r \), the remainder of division such that \(a = qm + r \), where \(q\) is the quotient and \(0 \leq r < m \).

If \(r\) were equal to \(m\), then \(a = qm + m = (q+1)m + 0\), meaning the actual remainder is 0. The two are congruent modulo \(m \), \(m \equiv 0 \pmod m \).

Usage in programming languages #

Usually, in programming languages, the modulo operator is denoted as %. For example, this is true in Python and C++. In both languages, the modulo operator computes the remainder of division a % m, but its behavior is different when a is negative.

  • In Python, the modulo result has the same sign as the divisor m which ensures mathematical consistency.
  • In C++, the modulo result has the same sign as the dividend a.

To make C++ modulo operator behave like Python, we can use the following expression: (a % m + m) % m. This follows from property 6 above.